#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <ctime>



/*****定义*****/
struct Node
{
    int data;
    struct Node *next;
};
typedef struct Node Node;
typedef struct Node *LinkList;



/*****随机生成一个单链表*****/
LinkList List_TailInsert(int l, LinkList &L) // 随机生成一个长度为l的单链表（未排序并且有头结点）
{
    int k = 1;
    int x = 0;
    L = (LinkList)malloc(sizeof(Node)); // 创建头结点
    LinkList s;
    LinkList r = L; // r为表尾指针
    // srand(time(0));//放在这一行会导致两组随机数差不多
    while (k <= l)
    {
        x = rand() % 101;
        s = (LinkList)malloc(sizeof(Node)); // 由系统生成一个Node型的结点，同时将该结点的起始位置赋值给指针变量s
        s->data = x;
        r->next = s;
        r = s;
        k = k + 1;
        printf("%d ", x);
    }
    r->next = NULL;
    printf("\n");
    return L;
}



/*****冒泡排序*****/
LinkList BubbleSort(LinkList &L) // 对单链表进行冒泡排序
{
    LinkList pa, pb, pc;
    int c = 0;
    pa = L->next;
    pb = L->next->next;
    pc = L->next;
    int j = 1;
    int l = 0; //求链表长度
    while (pc != NULL)
    {
        l = l + 1;
        pc = pc->next;
    }
    while (j < l)
    {
        if (pa->data > pb->data)
        {
            c = pb->data;
            pb->data = (int)pa->data;
            pa->data = c;
            j = 1;
        }
        else
        {
            j = j + 1;
        }
        pb = pb->next;
        pa = pa->next;
        if (pa->next == NULL && j != l)
        {
            j = 1;
            pa = L->next;
            pb = L->next->next;
        }
    }
    pc = L->next;
    while (pc != NULL)
    {
        printf("%d ", pc->data);
        pc = pc->next;
    }
    printf("\n");
    return L;
}



/*****输出一个单链表*****/
void printd(LinkList L)
{
    LinkList p = L->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}



/*****核心功能函数*****/
LinkList dik(int i, int k, LinkList &L)// delete >i <k
{
    if (i > k)
    {
        return NULL;
    }
    LinkList p, q, pre;
    p = L->next;
    q = L;
    pre = NULL;

    while (p->data <= i && p != NULL)
    {
        pre = p;
        p = p->next;
    }

    while (p->data < k && p != NULL)
    {
        q = p;
        p = p->next;
        delete q;
    }

    pre->next = p;
    return L;
}



/*****主函数*****/
int main()
{
    //生成一个单链表
    LinkList L = NULL;
    srand(time(0));
    printf("  生成的单链表：");
    List_TailInsert(12, L); // 随机生成一个长度为12（不算头结点）的单链表
    
    //冒泡排序（结合了输出功能）
    printf("排序后的单链表：");
    BubbleSort(L);  

    //输出i和k的值以及符合题意的单链表
    int i = 28; // i可以自由修改
    int k = 68; // k可以自由修改
    dik(i, k, L);
    printf("             i：%d\n", i);
    printf("             k：%d\n", k);
    printf("处理后的单链表：");
    printd(L);
    
    //防止运行后自动退出，需头文件【stdlib.h】
    system("pause"); 
}